def dag_count_paths(Adj):
    V = xrange(len(Adj)) 
    d = [0] * len(V)
    d[0] = 1
    for u in V:
        for v, _ in Adj[u]:
            d[v] += d[u]
    return d[-1]

if __name__=='__main__':
    from sys import maxint
    from pprint import pprint
    Adj = [[(1,5),(2,3)],[(3,6),(2,2)],[(3,7),(4,4),(5,2)], \
           [(5,1),(4,-1)],[(5,-2)],[]] #CLRS pp.592, in topo order
    print 'Adj: Adj[u] stores (v,w[u,v])'
    pprint(Adj)
    d = dag_count_paths(Adj)
    print '# of paths: ', d
